/*
* Copyright (c) 2013 City University of Hongkong.
*                    Cloud computing security group.
* 
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

/*
* graph_reduction.h - partial MC-SSTA and graph reduction.
*
* Authors: Xingliang Yuan     
* Emails:  xyuan86@gmail.com
*
*/

#ifndef GRAPH_REDUCTION_H
#define GRAPH_REDUCTION_H

#include "../algorithm/mc_utility.h"
#include "../graph/ff_graph.h"

class graph_reduction: public mc_utility
{
protected: 

    vector<float> mc_vertex_delay; // deterministic vertex delay
    vector<float> vertex_arrive_time; // vertex arrive time

    vector<unsigned long> mc_vertex_seed; // store random_seed

    //color label for DFS
    vector <unsigned int> color_label;
    vector <unsigned int> partitions;
    vector <edge> argument_path;
    bool argument_exist;
    unsigned int backup_vertex_num;
    unsigned int prime_path_num;

    unsigned int total_reduced_num;

    //vector<unsigned int> vertex_set; // vertex_set by topological order

    vector<unsigned int> vertex_delete_tag; // tag vertex is done by elimination

    vector<unsigned int> gray_set; //store gray vertexes
    vector <vector<edge>> gray_path_set; //store gray path
    //vector<unsigned int> gray_longest_path_depth; //store gray longest path

    /* 
     * gray vertex to gray ones reachable list; 
     * each path start from gray and end from gray;
     * using set to avoid different path to same end vertex.
     */
    set <set<unsigned int>> gray_reach_list; 

    /* 
     * gray vertex to gray ones full reachable list; 
     */
    vector <vector<unsigned int>> full_reach_list; 

    //vector<unsigned int> current_reach_list;

    void DFS_visit(class ff_graph& ff_obj, const unsigned int &vertex);

    void find_s_partition(class ff_graph& ff_obj, const unsigned int &vertex);

    void find_min_cut(class ff_graph& ff_obj);

    void cost_reduce(class ff_graph& ff_obj);

    /*  
    * description: generate deterministic vertex delay for one MC simulation
    * param: ff_graph instance, ith simulation for seed reproduce
    * return: 
    */
    void gen_mc_delay(class ff_graph& ff_obj, unsigned int ith_mc);

    /*  
    * description: pre-evaluate reachable gray vertex pairs
    * param: ff_graph instance 
    * return: 
    */
    void gen_reach_lists(class ff_graph& ff_obj);

    /*  
    * description: load graph (get edge set, gate_num, ff_num, edge_num)
    * param: 
    * return: 
    */
    void load_graph(char* benchmark, class ff_graph& ff_obj);

    /*  
    * description: load random gate delay for each vertex
    * param: 
    * return: 
    */
    void load_vertex_delay(char* benchmark, class ff_graph& ff_obj);

    /*  
    * description: check edge_{j, k} exists or not
    * param: edge source and sink vertex
    * return: valid edge; invalid edge(0, 0, 0.0)
    */
    struct edge edge_exist(unsigned int source, unsigned int sink, 
                        class ff_graph& ff_obj);

    /*  
    * description: delete fanin edge of v_i
    * param: v_i fanin edge
    * return: 
    */
    bool fanin_delete(struct edge fanin, class ff_graph& ff_obj);

     /*  
    * description: delete fanout edge of v_i
    * param: v_i fanout edge
    * return: 
    */
    bool fanout_delete(struct edge fanout, class ff_graph& ff_obj);

    /*  
    * description: vertex elimination for v_i
    * param: white vertex v_i
    * return: 
    */
    void vertex_elimination(unsigned int v, class ff_graph& ff_obj);

    /*  
    * description: partial STA and graph reduction
    *              following topological order for each MC simulation
    * param: 
    * return: 
    */
    void partial_sta(class ff_graph& ff_obj);

    /*  
    * description: partial STA and graph reduction
    *              following topological order for each MC simulation
    * param: 
    * return: 
    */
    void partial_sta_reduce(class ff_graph& ff_obj);

    /*  
    * description: create reduce graph file %benchmark%_rd.dag
    * param: 
    * return: 
    */
    void write_reduce_graph(char* benchmark, class ff_graph& ff_obj); 

public:
    /*  
    * description: partial MC-SSTA and graph reduction
    * param: 
    * return: 
    */
    void partial_mc_ssta(char* benchmark, unsigned int mc_num, 
                        class ff_graph& ff_obj);
    
};

#endif // GRAPH_REDUCTION_H

